package com.shexianyu.difficult;

/**
 * 700. 二叉搜索树中的搜索
 */
public class SearchBST {

    public TreeNode searchBST(TreeNode root, int val) {
        //若树为空，则返回null
        if (root == null) return null;
        //搜索到值返回root
        if (root.val == val) {
            return root;
        }
        //若值小于root.val 递归左子树
        if (val < root.val)
            return searchBST(root.left, val);
        //若值大于root.val 递归右子树
        if (val > root.val)
            return searchBST(root.right, val);
        return null;
    }

    /**
     * 参考答案简易写法
     *
     * @param root 树
     * @param val  搜索值
     * @return
     */
    public TreeNode searchBST1(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}
